package day5;

import java.util.*;

public class ch3 {


    public static int sum = 0;
    public int pathSum(TreeNode root, int targetSum) {
        sum = 0;
        HashMap<Long,Integer> map = new HashMap<>();
        map.put(0l,1);
        fun1(root,0l,targetSum,map);


        return sum;

    }

    public void fun1(TreeNode node,long num,int targetSum,HashMap<Long,Integer> map){
        if(node==null) return;

        num += node.val;
        sum += map.getOrDefault(num-targetSum,0);

        map.put(num,map.getOrDefault(num,0)+1);

        fun1(node.left,num,targetSum,map);
        fun1(node.right,num,targetSum,map);

        map.put(num,map.get(num)-1);


    }


    //199
    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node =  queue.poll();
                if(i==size-1) list.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
        }

        return list;

    }

    //114
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        fun2(root,list);

        int len = list.size();
        for (int i = 1; i < len; i++) {
            TreeNode m = list.get(0);
            TreeNode n = list.get(1);
            m.left = null;
            m.right = n;
            n.left = null;
            n.right = null;
        }

        return;


    }

    public void fun2(TreeNode node,List<TreeNode> list){
        list.add(node);
        fun2(node.left,list);
        fun2(node.right,list);
    }


    public void fun3(TreeNode root){
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }

    }




}
